package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 子集 II
 */

public class Code090 {
    public static void main(String[] args) {
        int[] nums = {4, 4, 4, 1, 4};
        System.out.println(new Code090().subsetsWithDup(nums));
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 先排序，重要！
        backtrack(0, new ArrayList<>(), result, nums);
        return result;
    }

    // 从答案视角
    private void backtrack(int index, List<Integer> list, List<List<Integer>> result, int[] nums) {
        result.add(new ArrayList<>(list));

        for (int i = index; i < nums.length; i++) {
            // 跳过重复元素：如果当前元素与前一个元素相同，且前一个元素不是当前选择的起点
            if (i > index && nums[i] == nums[i - 1]) {
                continue;
            }

            list.add(nums[i]);
            backtrack(i + 1, list, result, nums);
            list.remove(list.size() - 1);
        }
    }
}
